package solution.list;

import java.util.LinkedList;

/**
 * @author <a href="www.sureinterview.com">SureInterview</a>
 * 
 *         Check http://www.sureinterview.com/wiki/Shwqst/903001
 */
public class QueueWithMax<T extends Comparable<T>> {

	/*
	 * The auxiliary queue is in descending order. The head is the current
	 * maximum value and the tail is the last inserted value.
	 */
	LinkedList<T> auxiQ = new LinkedList<T>();

	/*
	 * The data queue.
	 */
	LinkedList<T> dataQ = new LinkedList<T>();

	/**
	 * Append the data at the end of queue. Adjust auxiliary queue to supports
	 * the getMax operation.
	 * 
	 * @param data
	 */
	public void addLast(T data) {
		// insert data to the data queue.
		dataQ.add(data);

		// adjust the auxiliary queue.
		while (!auxiQ.isEmpty() && auxiQ.getLast().compareTo(data) < 0) {
			auxiQ.removeLast();
		}
		auxiQ.add(data);
	}

	/**
	 * get the head value.
	 * 
	 * @return
	 */
	public T getFirst() {
		return dataQ.getFirst();
	}

	/**
	 * get the max in O(1).
	 * 
	 * @return
	 */
	public T getMax() {
		if (auxiQ.isEmpty())
			return null;
		return auxiQ.getFirst();
	}

	/**
	 * remove the head.
	 * 
	 * @return
	 */
	public T removeFirst() {
		T data = dataQ.removeFirst();

		// adjust the auxiliary queue. Because the previous max is removed, the
		// head (which is the current max) should be removed too.
		if (data == auxiQ.getFirst()) {
			auxiQ.removeFirst();
		}
		return data;
	}

}
